package ee.ttu.serge.container.priorityqueue;

import ee.ttu.serge.container.dynamicarray.DynamicArray;

public class PriorityQueue<T extends Comparable<T>> {

   private DynamicArray<T> array;
   
   public PriorityQueue() {
      create();
   }
   
   /**
    * Loob prioriteetjärjekorra O(1)
    */
   private void create() {
      array = new DynamicArray<T>();
      array.create(5);
   }
   /**
    * Lisab arvu x prioriteetjärjekorda O(lg n)
    */
   public void enqueue(T x) {
      array.add(x); //lisab puu tippu uue elemendi
      int pos = array.len() - 1; //viimane element
      T tmp;
      while (pos > 0 && array.get(pos).compareTo(array.get(pos / 2)) == -1) { //kui kõrgemas harus on suurem
          tmp = array.get(pos);
          array.put(array.get(pos / 2), pos); //paneme madalama kõrgemale
          array.put(tmp, pos / 2); //paneme kõrgema madalamale
          pos /= 2; //liigume 1 taseme võrra alla
      }

   }
   /**
    * Väljastab ja eemaldab minimaalse elemendi O(lg n)
    */
   public T dequeue() {
      if (array.len() == 0) {
         return null;
      }

      T result = array.get(0); //minimaalne element on alati tipus
              
      T tmp = array.rem(); //võtame viimase elemendi arrays ära
      array.put(tmp, 0);

      int pos = 1;
      int shift;
      int nextLevel;
      while ((nextLevel = pos * 2) <= array.len()) { // continue until no children
         shift = 0; // vasak laps
         if (nextLevel + 1 <= array.len()) { // kui on olemas parempoolne laps
            if (array.get(nextLevel - 1).compareTo(array.get(nextLevel)) == 1) { // kui parempoolne laps on väiksem
               shift = 1; // parem laps
            }
         }

         if (array.get(nextLevel + shift - 1).compareTo(array.get(pos - 1)) == -1) { // kui valitud laps on väiksem kui vanem
            // vahetame noded
            tmp = array.get(nextLevel + shift - 1);
            array.put(array.get(pos - 1), nextLevel + shift - 1);
            array.put(tmp, pos - 1);
         } else {
            break;
         }

         pos = nextLevel + shift; // läheme edasi valitud haru pidi
      }
      return result;

   }
   /**
    * Väjastab true, kui prioriteetjärjekord on tühi O(1)
    */
   public boolean isEmpty() {
      return array.len() == 0;
   }
   
}
